package likou.tanxin;

/**
 * @Info:
 * @Author: Tangxz
 * @Date: 2020/09/13 16:04
 */
public class _316 {
    public static void main(String[] args) {
        System.out.println(removeDuplicateLetters("bbcab"));
    }

    public static String removeDuplicateLetters(String s) {
        // find pos - the index of the leftmost letter in our solution
        // we create a counter and end the iteration once the suffix doesn't have each unique character
        // pos will be the index of the smallest character we encounter before the iteration ends
        //找到pos-我们解决方案中最左边字母的索引
        //我们创建一个计数器，并在后缀没有每个唯一字符时结束迭代
        //pos是迭代结束前遇到的最小字符的索引
        int[] cnt = new int[26];
        int pos = 0;
        for (int i = 0; i < s.length(); i++) {
            cnt[s.charAt(i) - 'a']++;
        }
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) < s.charAt(pos)) {
                pos = i;
            }
            if (--cnt[s.charAt(i) - 'a'] == 0) {
                break;
            }
        }
        // our answer is the leftmost letter plus the recursive call on the remainder of the string
        // note that we have to get rid of further occurrences of s[pos] to ensure that there are no duplicates
        return s.length() == 0 ? "" : s.charAt(pos) + removeDuplicateLetters(s.substring(pos + 1).replaceAll("" + s.charAt(pos), ""));
    }

//    public static String removeDuplicateLetters(String s) {
//        char[] chars = s.toCharArray();
//        int[] nums = new int[26];
//        Deque<Character> deque = new LinkedList<>();
//        for (int i = 0; i < chars.length; i++) {
//            nums[chars[i] - 97]++;
//        }
//        int nowMin = searchMinIndex(nums);//当前最小的那一位的下标志
//        //边排序边找
//        //最小的那一位，遇见就变为0，遇见直接放。
//        //不知最小的那一位，没有了就直接放！
//        String daan = "";
//        for (int i = 0; i < chars.length; i++) {
//            if (chars[i] - 97 == nowMin) {
//                int nowMax = chars[i];
//                while (deque.size()>0){
//                    char last = deque.pollFirst();
//                    if (last<nowMax){
//                        nowMax = last;
//                        daan = daan + last;
//                        nums[last-97] = 0;
//                    }
//                }
//                daan = daan + chars[i];
//                nums[nowMin] = 0;
//                nowMin = searchMinIndex(nums);
//            }else {
//                int nowIndex = chars[i] - 97;
//                if (nums[nowIndex]>1){
//                    deque.offerLast(chars[i]);
//                    nums[nowIndex]--;
//                }else if (nums[nowIndex]==1){
//                    int nowMax = chars[i];
//                    while (deque.size()>0){
//                        char last = deque.pollFirst();
//                        if (last<nowMax){
//                            nowMax = last;
//                            daan = daan + last;
//                            nums[last-97] = 0;
//                        }
//                    }
//                    daan = daan + chars[i];
//                    nums[nowIndex]--;
//                }
//            }
//        }
//        return daan;
//    }
//
//    //找当前最小的那一位
//    public static int searchMinIndex(int[] nums) {
//        for (int i = 0; i < nums.length; i++) {
//            if (nums[i] > 0) {
//                return i;
//            }
//        }
//        return -1;
//    }
}
